package test0309;

import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 利用扩展先序序列构建二叉树
 * 输入: AB#D##C##
 */
public class Main01 {

    public static void main(String[] args) {
        System.out.println("请输入扩展先序序列构建二叉树: ");
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        BinaryTree.TreeNode biTree = BinaryTree.createBiTree(str);
        System.out.println("先序遍历: ");
        BinaryTree.preorder(biTree);
    }
}

/**
 * 二叉树
 */
@SuppressWarnings({"all"})
class BinaryTree {

    static class TreeNode {

        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 利用扩展先序序列构建二叉树
    static int  i = 0; // 用于遍历字符串
    static String str = "";

    // 根据先序遍历序列构建二叉树 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
    public static TreeNode createBiTree(String str){
        // 如果遇到“#”则为空
        if(str.charAt(i) == '#'){
            i++;
            return null;
        }
        // 否则按照val构造树节点
        TreeNode root = new TreeNode(str.charAt(i));
        i++;
        // 获取左子树和右子树的根节点 构造出二叉树
        root.left = createBiTree(str);
        root.right = createBiTree(str);
        // 最后将根节点返回
        return root;
    }


    // 先序遍历，用于测试
    public static void preorder(TreeNode root){
        if (root == null){
            return;
        }
        System.out.println(root.val);
        preorder(root.left);
        preorder(root.right);
    }
}